package demo4;

public class MyLinkList implements IMyLink {
    public static class node {
        public int val;
        public node next;

        public node(int val) {
            this.val = val;
        }
    }

    public node hand;

    public void createList() {

    }

    @Override
    public void Traversal() {
        node car = this.hand;
        while (car != null) {
            System.out.print(car.val + " ");
            car = car.next;
        }
        System.out.println();
    }

    public void Traversal1(node hand) {
        node car = hand;
        while (car != null) {
            System.out.print(car.val + " ");
            car = car.next;
        }
        System.out.println();
    }

    @Override
    public int size() {
        node car = this.hand;
        int count = 0;
        while (car != null) {
            count++;
            car = car.next;
        }
        return count;
    }

    @Override
    public boolean exist(int index) {
        node car = this.hand;
        while (car != null) {
            if (car.val == index) {
                return true;
            }
            car = car.next;
        }
        return false;
    }

    @Override
    public void FirstAdd(int index) {
        node node = new node(index);
        node.next = hand;
        hand = node;
    }

    @Override
    public void EedAdd(int index) {
        node node = new node(index);
        node car = this.hand;
        if (hand == null) {
            hand = node;
        } else {
            while (car.next != null) {
                car = car.next;
            }
        }
        if (car != null) {
            car.next = node;
        }
    }

    @Override
    public void remove(int index) {
        if (hand == null) {
            return;
        }
        if (hand.val == index) {
            hand = hand.next;
            return;
        }
        node car = find(index);
        if (car == null) {
            return;
        }
        car.next = car.next.next;
    }

    public node find(int x) {
        node car = hand;
        while (car.next != null) {
            if (car.next.val == x) {
                return car;
            }
            car = car.next;
        }
        return null;
    }

    @Override
    public void RemoveAllkey(int index) {
        node prv = hand;
        node car = hand.next;
        while (car != null) {
            if (car.val == index) {
                prv.next = car.next;
            } else {
                prv = prv.next;
            }
            car = car.next;
        }
        if (hand.val == index) {
            hand = hand.next;
        }
    }

    @Override
    public void clear(node hand) {
        hand = null;
    }

    @Override
    // 将链表逆序打印
    public node ReveseList() {
        if (hand == null) {
            return null;
        }
        if (hand.next == null) {
            return hand;
        }
        node car = hand.next;
        hand.next = null;
        while (car != null) {
            node carNext = car.next;
            car.next = hand;
            hand = car;
            car = carNext;
        }
        return hand;
    }

    @Override
    public void clear() {
        hand = null;
    }

    public int midNode() {
        if (hand == null) {
            return 0;
        }
        if (hand.next == null) {
            return hand.val;
        }
        node pow = hand;
        node slow = hand;
        while (true) {
            pow = pow.next.next;
            if (pow != null) {
                if (pow.next != null) {
                    slow = slow.next;
                } else return slow.next.val;
            } else return slow.next.val;
        }
    }

    public node MergeTwoList(node hand1, node hand2) {
        MyLinkList.node newHead = new node(-1);
        MyLinkList.node temp = newHead;
        while (hand1 != null && hand2 != null) {
            if (hand1.val > hand2.val) {
                temp.next = hand2;
                hand2 = hand2.next;
            } else {
                temp.next = hand1;
                hand1 = hand1.next;
            }
            temp = temp.next;
        }
        if (hand2 == null) {
            temp.next = hand1;
        } else {
            temp.next = hand2;
        }
        return newHead.next;
    }

    public node FindKthToTail(node head, int k) {
        node fast = head;
        node slow = head;
        if (hand == null) {
            return null;
        }
        while (k != 1) {
            if (fast.next != null) {
                fast = fast.next;
                k--;
            } else return null;
        }
        while (fast.next != null) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }

    public node partition(node pHead, int x) {
        if (hand == null) {
            return null;
        }
        node ps = null;
        node pe = null;
        node as = null;
        node ae = null;
        node temp = hand;
        while (temp != null) {
            if (temp.val < x) {
                if (ps == null) {
                    pe = temp;
                    ps = temp;
                } else {
                    pe.next = temp;
                    pe = pe.next;
                }
            } else {
                if (as == null) {
                    ae = temp;
                    as = temp;
                } else {
                    ae.next = temp;
                    ae = ae.next;
                }
            }
            temp = temp.next;
        }
        if (ps == null) {
            return as;
        }
        pe.next = as;
        if (as != null) {
            ae.next = null;
        }
        return ps;
    }

    public boolean chkPalindrome(node head) {
        node fast = head;
        node slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        node car = slow.next;
        while (car != null) {
            node newhand = car.next;
            car.next = slow;
            slow = car;
            car = newhand;
        }
        while (head != slow) {
            if (head.val != slow.val) {
                return false;
            } else {
                slow = slow.next;
                head = head.next;
            }
            if (hand.next.val == slow.val) {
                return true;
            }
        }
        return true;
    }

    // 求相交链表的相交节点
    public node getIntersectionNode(node headA, node headB) {
        int lenA = 0;
        int lenB = 0;
        node p1 = headA;
        node p2 = headB;
        while (p1 != null) {
            lenA++;
            p1 = p1.next;
        }
        while (p2 != null) {
            lenB++;
            p2 = p2.next;
        }
        p1 = headA;
        p2 = headB;
        int len = lenA - lenB;
        if (len < 0) {
            {
                p1 = headB;
                p2 = headA;
                len = lenB - lenA;
            }
        }
        while (len != 0) {
            p1 = p1.next;
            len--;
        }
        while (p1 != p2) {
            p1 = p1.next;
            p2 = p2.next;
        }
        p1.next = null;
        return p1;
    }

    public void Cycle(node hand) {
        node cur = hand;
        node p1 = hand;
        while (cur.next != null) {
            cur = cur.next;
        }
        cur.next = p1.next.next;
    }

    // 求环形链表的入口点
    public int hasCycle(node head) {
        node fast = head;
        node slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (slow == fast) {
                slow = head;
                while (slow != fast) {
                    slow = slow.next;
                    fast = fast.next;
                }
                return slow.val;
            }
        }
        return -1;
    }
}
